package everydayone.superEggDrop;

import java.util.Arrays;

/**
 * @Date 2020/04/11
 * @author 王光浩
 * @Thinking 使用DP+备忘录
 */
public class MyMethodTwo {
	private int[][] help;
	public int superEggDrop(int K,int N) {
		help=new int[K+1][N+1];
		for(int i=help.length-1;i>=0;i--)
			for(int j=help[0].length-1;j>=0;j--)
				help[i][j]=-1;
		recursively(K,N);
		return help[K][N];
	}
	private int recursively(int K,int N) {
		if(K==1)help[K][N]=N; 
		if(N==0)help[K][N]=0;
		if(help[K][N]!=-1)return help[K][N];
		int res=Integer.MAX_VALUE;
		for(int i=1;i<=N;i++) {
			res=Math.min(res, 1+Math.max(superEggDrop(K-1,i-1), superEggDrop(K,N-i)));
		}
		help[K][N]=res;
		return help[K][N];
	}
	public static void main(String[] args) {
		MyMethodTwo test=new MyMethodTwo();
		System.out.println(test.superEggDrop(2, 14));
	}
}
